package com.xinheyun.demo.leetcode;

import java.util.Arrays;

/**
 * @description: TODO
 * @author: Sarah
 * @modified By: Sarah
 * @date: Created in 2021/8/31 11:37
 * @version:v1.0
 */
public class test416 {

    public static void main(String[] args) {
        test416 test416 = new test416();
        int[] ints = {8,4};
        boolean b = test416.canPartition(ints);

    }
    
    public boolean canPartition(int[] nums) {
        int sum = Arrays.stream(nums).sum();
        if (sum % 2 == 1) {
            return false;
        }
        int target = sum / 2;
        boolean[] dp = new boolean[target + 1];
        dp[0] = true;
        for (int i = 1; i <= target; i++) {
            dp[i] = false;
        }
        for (int num : nums) {
            for (int i = target; i >= num; i--) {
                dp[i] = dp[i] || dp[i - num];
            }
        }
        return dp[target];
    }
    
    
}
